//
// Created by Jisam on 2024/6/29.
//
#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

void printPermutations(vector<int>& nums, vector<int>& used, vector<int>& permutation, int n) {
    if (permutation.size() == n) {
        for (int num : permutation) {
            cout << setw(5) << num ;
        }
        cout << endl;
        return;
    }

    for (int i = 0; i < n; i++) {
        if (used[i]) continue; // 如果数字已经被使用，则跳过
        used[i] = true; // 标记数字为已使用
        permutation.push_back(nums[i]); // 将数字添加到排列中
        printPermutations(nums, used, permutation, n); // 递归处理下一个位置
        used[i] = false; // 回溯，撤销数字的使用标记
        permutation.pop_back(); // 回溯，撤销数字的添加
    }
}

template<typename T> T fast_pow(T b, T e, T m) {
    T r = 1;
    while (e) {
        if (e & 1) r = (r * b) % m;
        b = (b * b) % m;
        e >>= 1;
    }
    return r;
}

int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

vector<int> zFunction(string s) {
    int n = s.size();
    vector<int> z(n + 1);
    z[0] = n;
    for (int i = 1, j = 1; i < n; i++) {
        z[i] = max(0, min(j + z[j] - i, z[i - j]));
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if (i + z[i] > j + z[j]) {
            j = i;
        }
    }
    return z;
}
int main() {
    // 时间

    cout << fast_pow(5,122,INT_MAX) << endl;
    cout << qmi(5,122,INT_MAX) << endl;
    //    int n;
//    cin >> n;
//    vector<int> nums(n);
//    vector<int> used(n, false);
//    vector<int> permutation;
//
//    for (int i = 0; i < n; i++) {
//        nums[i] = i + 1;
//    }
//
//    printPermutations(nums, used, permutation, n);

    return 0;
}
